package org.example.myleet.p498;

public class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int i = 0, end = m * n;
        int[] result = new int[m * n];
        int row = 0, column = 0;
        //true - from bottom left to top right, false - reverse
        boolean toTopRight = true;
        while (i < end) {
            result[i++] = mat[row][column];
            if (toTopRight) {
                //向右上方走一格
                --row;
                ++column;
                if (row < 0 || column >= n) {
                    toTopRight = false;
                    if (row < 0 && column >= n) {
                        //已突出对角线，转到下一行
                        row += 2;
                        --column;
                    } else {
                        if (row < 0) {
                            //只是行突出了，撤回来
                            ++row;
                        }
                        if (column >= n) {
                            //已突出右边界，转到下一行
                            --column;
                            row += 2;
                        }
                    }
                }
            } else {
                //向左下方走一格
                ++row;
                --column;
                if (row >= m || column < 0) {
                    toTopRight = true;
                    if (row >= m && column < 0) {
                        //已突出对角线，转到下一列
                        --row;
                        column += 2;
                    } else {
                        if (row >= m) {
                            //已突出下边界，转到下一列
                            --row;
                            column += 2;
                        }
                        if (column < 0) {
                            //只是列突出了，撤回来
                            ++column;
                        }
                    }
                }
            }
        }
        return result;
    }
}
